package Testdemo4;


import linklist.MyLinkedList.LinkedNode;
import singlinklist.MySingleLinkedList;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:周次煜
 * Date: 2024-05-27
 * Time：13:05
 */
public class Test2 {

    public static void main1(String[] args) {
        System.out.println(modifyString("j?qg??b"));
    }


    public static String modifyString(String ss) {
        int n = ss.length();
        char[] s=  ss.toCharArray();

        // 用来记录前一个字符
        char  tmp = 0;

        String ret = "";
        // 进行遍历
        for(int i=0 ; i < n ; i++) {

            // 一旦我们找到 ?
            // 就判断
            if(s[i]=='?') {

                // 在内部进行循环判断
                for(char j = 'a'; j <= 'z' ; ) {
                    if( (i-1 >= 0)  && (s[i-1] == j) ) {
                        j++;
                    } else if (((i + 1) < n)  &&  (j == s[i+1])) {
                        j++;
                    }  else {


                        // 为了防止两个连续 的 ？ ？ 出现
                        // 一旦出现上次赋值的
                        if (j==tmp) {
                            // 我们就 ++
                            j++;
                            // 并且继续进入循环
                            continue;
                        }


                        ret += j;

                        // 记住上次赋值过的字母
                        tmp = j;
                        break;

                    }
                }
            } else {
                // 如果没有就直接连接
                ret += s[i];
            }


        }

        return ret;
    }







    /**
     *  提莫攻击
     *   方法： 超过或等于的这个的长度，我们就用 sum += 长度 -1 的大小
     *
     *   未超过的 我们就直接加上我们 dartion 的 跳跃长度
     * @param timeSeries 起点数组
     * @param duration  跳跃的区间
     * @return 返回总的跳跃长度
     */

    public int findPoisonedDuration(int[] timeSeries, int duration) {
        int n= timeSeries.length;
        int sum = 0;
        for(int i = 0; i < n-1; i++) {
            if((timeSeries[i] + duration - 1) < timeSeries[i+1]   ) {
                // 未超出就计算持续时间
                sum += duration;
            }  else {

                // 刚好到达下一秒开始
                // 超出就计算计算宽度 - 1
                sum += timeSeries[i+1] - timeSeries[i]   ;
            }
        }

        // 最终算出最后一个数的总和
        sum += duration;

        return sum ;
    }


    public static void main2(String[] args) {
//        System.out.println(countAndSay(4));
//        System.out.println((4-1)+"3");

        System.out.println(Character.isAlphabetic('-'));
//        char[] array = new  char[10];
//        for (int i = 0; i < 10; i++) {
//            System.out.printf("%d\n",(int)array[i]);
//        }
    }



    /**
     * 计算外观数列
     * 非递归的思路
     *
     * 先循环一直走
     * 后用双指针算法
     *
     * @param n 外观次数
     * @return 返回字符串
     *
     */




    public static String countAndSay(int n) {

        int[] nums = new  int[]{1};
        // 先进行循环
        while(n > 1) {

            int len = nums.length;
            // 用来记录每段的个数
            int[] count= new int[2*len];
            int countIndex = 0;

            // 进行双指针统计
            int left=0 , right=0;
            while(right < len) {


                if(nums[right] == nums[left]) {
                    // 如果相等就让 right 一直往右走
                    right++;

                } else {
                    // 不相等时就进入count表

                    // 进入个数
                    count[countIndex++] = (right -left);

                    // 进入当前元素
                    count[countIndex++] = nums[left];

                    // 最终让 left 到 right的位置
                    left = right;
                }



            }

            // 处理边界情况
            // 进入个数
            count[countIndex++] = (right -left);

            // 进入当前元素
            count[countIndex++] = nums[left];


            // 最把count，拷贝给 nums
            nums =  Arrays.copyOf(count,countIndex);
            n--;
        }




        String ret = "";

        // 转化成需要的形式
        for (int i = 0; i < nums.length; i++) {

           ret += nums[i];
        }



        return ret;
    }


    /**
     * 求外观数列
     * 递归思路
     *
     *
     */



    public  String countAndSay1(int n) {
        if(n==1) {
            return "1";
        }

        int left =0 ,right=0;
        // 先的得到上一步的 字符串
        String s = countAndSay1(n-1);
        char[] chs = s.toCharArray();
        int count = 0;
        while( right < chs.length  && chs[left] == chs[right] ) {
            right++;
        }

        return (right-left) + countAndSay1(n-1);
    }


    public static void main3(String[] args) {
        System.out.println(convert("PAYPALISHIRING", 4));
    }

    /**
     * Z 字形变换
     * 将一个字符串转换为 从上到下 ，从左到右是 Z 字形的字符矩阵
     * 并且 普通的输出该字符矩阵
     *
     * @param s 目标字符串
     * @param numRows 要求的行数
     * @return  返回该 Z字形的字符串
     *
     */

    public static String convert(String s, int numRows) {
        int n=s.length();

        // 转化为字符数组
        char[] chs= s.toCharArray();


        // 创造一个二维的字符矩阵
        char[][] tmp= new char[1000][1000];
        int row=0,col=0;

        // 遍历整个字符数组
        for(int k = 0 ; k < n ; ) {

            // 填写 Z 的上面 和 Z 的下面
            while(k < n && row < numRows) {
                // 进行赋值
                tmp[row][col] = chs[k];
                k++;
                row++;
            }



            // 开始拐弯
            row -= 2;

            if (row < 0) {
                row = 0;
            }
            col++;

            // 填写 Z 的中间
            while(k < n && row > 0) {
                tmp[row][col] = chs[k];
                k++;
                row--;
                col++;
            }

        }


        // 进行输出
        StringBuilder ret = new StringBuilder();
        for(int i=0;  i < numRows ; i++) {
            for(int j = 0; j < col ; j++) {

                // 判断是否是字母 ， ',' 和  '.'
                if(Character.isAlphabetic(tmp[i][j]) ||
                        tmp[i][j]==',' || tmp[i][j] == '.') {
                    // 一旦成立就 附加
                    ret.append(tmp[i][j]);
                }
            }
        }



        // 返回横向的字符串
        return ret.toString();

    }


    /**
     * 不同路径问题
     * 从左上角到啊右下角的路径种类
     *
     * @param m 行数
     * @param n 列数
     * @return 返回路径的种类
     */

    public int uniquePaths(int m, int n) {

        // 先构建一个状态转移方程
        int[][] dp = new int[m][n];

        // 先填左边界
        for(int i =0 ; i < m ; i++) {
            dp[i][0] = 1;
        }

        // 填上边界
        for(int j=0; j < n ;j++)  {
            dp[0][j] =1;
        }

        // 进行状态转移
        for(int i=1; i < m ; i++) {
            for(int j=1; j < n ; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }

        return dp[m-1][n-1];
    }


    /**
     * 外观数列
     *
     * 递归实现
     *
     * 递归本质值需要计算 最后一层 和 第一层的个数
     *
     * @param n 层数
     * @return 返回当前值
     */


    public String countAndSay2(int n) {
        // 外观数列
        // 递归实现


        if(n==1) {
            // 当层数为 1 就直接返回 1
            return "1";
        }

        String str = countAndSay2(n-1);

        // 用一个字符串来连接
        StringBuilder stringBuilder = new StringBuilder();
        // 用 count 来统计每个字符个数
        int count = 1;

        // 遍历整个字符串
        for(int i =1; i < str.length() ; i++) {



            // 得到前面数
            char chleft = str.charAt(i-1);
            // 得到后面数
            char chright = str.charAt(i);
            if(chleft == chright) {
                // 相等 count 就++
                count++;
            } else {
                // 不等就进入 字符串
                stringBuilder.append(count);
                stringBuilder.append(chleft);

                // 不要忘记讲count 重新置为 1
                count=1;
            }





        }

        // 处理边界未计算进入的情况
        stringBuilder.append(count);
        stringBuilder.append(str.charAt(str.length()-1));

        // 返回该层的字符串
        return stringBuilder.toString();
    }


    /**
     * 不同路径 2
     *
     * 在有障碍物的前提下，寻找到达目的地的所有路径的可能
     *
     * 有障碍物置为状态表示为 0
     * 无障碍物时， 利用转态转移方程来求路径
     * @param obstacleGrid  路径状况
     * @return 返回所有可能的总数
     *
     */

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {



        // 先得到行数和列数
        int row = obstacleGrid.length;
        int col = obstacleGrid[0].length;

        // 构建一个转态转移数组
        int[][] dp = new int[row+1][col+1];


        // 初始化
        dp[0][1] = 1;

        // 开始进行状态转移
        for(int i = 1; i <= row ;i++) {
            for(int j= 1; j <= col ; j++) {
                if(obstacleGrid[i-1][j-1]==1) {
                    // 遇到 1 就改为 0
                    dp[i][j]=0;
                } else {
                    // 状态转移方程
                    dp[i][j]= dp[i][j-1] + dp[i-1][j];
                }
            }
        }


        return dp[row][col];
    }


    /**
     * 数青蛙
     * 根据青蛙的叫声来数
     *
     * @param croakOfFrogs 青蛙的叫声
     * @return 返回青蛙的个数
     */

    public int minNumberOfFrogs1(String croakOfFrogs) {
        // 处理 边界特殊情况
        if(croakOfFrogs.length() < 5) return -1;


        // 利用哈希表来统计
        int[] hash = new int[26];

        // 转化为字符数组
        char[] str =  croakOfFrogs.toCharArray();

        // 遍历统计
        for(int i=0; i < str.length ; i++) {
            hash[str[i]-'a']++;
        }

        // 以第一位的字符出现的次数为基准值
        int count = hash[str[0]-'a'];

        for(int i = 1 ; i < str.length ; i++) {
            if(count != hash[str[i]-'a']) {
                return -1;
            }
        }

        // 处理只有一只青蛙的特殊情况
        if(croakOfFrogs.substring(0,5).equals("croak")) {
            return -1;
        }

        return count;
    }


    public static void main4(String[] args) {
        System.out.println(minNumberOfFrogs("crcoakroak"));
    }


    public static int minNumberOfFrogs(String croakOfFrogs) {
        int len = croakOfFrogs.length();
        // 处理边界 不符合的情况
        if(len < 5) return -1;

        int wid = len;

        // 转化为字符数组
        char[] str =  croakOfFrogs.toCharArray();

        // 当做返回值
        int ret =0;

        char tmp = 'c';
        for(int left = 0, right = 0 ; right < len ; right++) {


            // 按照次序寻找
            if(tmp == str[right]) {
                switch(tmp) {
                    case 'c' :
                        tmp = 'r';
                        str[right] = '#';
                        break;
                    case 'r' :
                        tmp = 'o';
                        str[right] = '#';
                        break;
                    case 'o' :
                        tmp = 'a';
                        str[right] = '#';
                        break;
                    case 'a' :
                        tmp = 'k';
                        str[right] = '#';
                        break;
                    case 'k' :
                        str[right] = '#';

                        // 记录最小宽度
                       wid= Math.min(wid,right-left+1);

                        tmp = 'c';
                        left++;
                        ret++;

                        while(left < len &&  str[left] != 'c') {
                            left++;
                        }

                        // 从 c 的位置重新开始遍历 “croak”
                        right = left-1;

                        break;
                }

            }





        }




        if (tmp != 'c') return  -1;

        if (wid==5) return  1;

        return ret;
    }


    /**
     * 数青蛙
     * 每遍历一个字符就寻找前面有没有这个字符
     * 方法 一: Switch 判断
     *
     * @param croak 青蛙叫声
     * @return  返回青蛙的个数
     */

    public  int minNumberOfFrogs2(String croak) {
        int len = croak.length();

        // 用一个额外的数组来管理
        char[] str = croak.toCharArray();
        // 创建一个哈希表
        int[] hash = new int[5];

        for(int i=0; i < len ; i++) {
            char ch = str[i];
            // 进行分支讨论
            switch(ch) {
                case 'c' :
                    //  注意这里查看第一个字符时
                    // 需要向最后一位字符看
                    if(hash[4]!= 0) {
                        hash[4]--;
                    }

                    hash[0]++;
                    break;
                case 'r' :
                    // 当前一位字符出现过
                    // 我们就减去一个
                    if(hash[0]!= 0) {
                        hash[0]--;

                    } else {
                        // 处理特殊减少的 'c'
                        hash[1]++;
                    }
                    // 自身要加上一位
                    hash[1]++;
                    break;
                case 'o' :
                    if(hash[1]!= 0) {
                        hash[1]--;
                    }
                    hash[2]++;
                    break;
                case 'a' :
                    if(hash[2]!= 0) {
                        hash[2]--;
                    }
                    hash[3]++;
                    break;
                case 'k' :
                    if(hash[3]!= 0) {
                        hash[3]--;
                    }
                    hash[4]++;
                    break;
            }




        }


        // 查找前面是否有多余的值
        for(int i=0; i<4; i++) {
            if(hash[i]!=0) {
                return -1;
            }
        }


        return  hash[4];
    }


    /**
     * 数青蛙
     * 每遍历一个字符就寻找前面有没有这个字符
     * 方法 一: 用临时数组来来管理
     * 得出下标即可
     *
     * @param croak 青蛙叫声
     * @return  返回青蛙的个数
     */

    public int minNumberOfFrogs3(String croak) {
        int len = croak.length();

        // 用一个额外的数组来管理
        char[] tmp = {'c','r','o','a','k'};
        char[] str = croak.toCharArray();

        // 创建一个哈希表
        int[] hash = new int[5];

        for(int i=0; i < len ; i++) {
            char ch = str[i];

            // 遍历查找临时数组得出下表
            for(int j = 1; j < 5;j++) {
                // 判断最前面的字符
                if(ch == 'c' ) {
                    if(hash[4] != 0) {
                        hash[4]--;
                    }
                    hash[0]++;
                    break;
                }

                // 得出下标位置
                if(ch == tmp[j]) {
                    // 前面一个位置出现过
                    if(hash[j-1] != 0) {
                        hash[j-1]--;
                        hash[j]++;
                    } else {
                        // 前面一个位置未出现过
                        hash[j]+= 2;
                    }
                }
            }


        }


        // 查找前面是否有多余的值
        for(int i=0; i<4; i++) {
            // 只要前面字符出现的次数多余
            // 就返回 -1
            if(hash[i]!=0) {
                return -1;
            }
        }


        return  hash[4];
    }


    /**
     * 数青蛙
     * 方法三
     * 用 indexmap 来确定下标位置
     * @param croak
     * @return
     */

    public int minNumberOfFrogs4(String croak) {
        int len = croak.length();

        // 用一个额外的 indexmap 来管理下标
        Map<Character, Integer>  indexmap = new HashMap<>();
        char[] str = croak.toCharArray();
        String dest = "croak";
        int destlen =  dest.length();

        // 创建一个哈希表
        int[] hash = new int[destlen];

        // 讲下标进入 map 中
        for(int i=0; i < destlen; i++) {
            indexmap.put(dest.charAt(i),i);
        }

        for(int i=0; i < len ; i++) {
            char ch = str[i];

            // 在 indexmap 中寻找值即可
            if(ch==dest.charAt(0)) {
                // 特殊的第一个位置
                if(hash[destlen-1]!=0) {
                    hash[destlen-1]--;
                }

                // 自身加上一个
                hash[0]++;
            } else {
                // 得到当前字符位置的小标
                int index = indexmap.get(ch);
                if(hash[index-1]!= 0) {
                    // 前面的字符存在时
                    hash[index-1]--;
                    hash[index]++;
                } else {
                    return -1;
                }
            }


        }


        // 查找前面是否有多余的值
        for(int i=0; i<4; i++) {
            // 只要前面字符出现的次数多余
            // 就返回 -1
            if(hash[i]!=0) {
                return -1;
            }
        }


        return  hash[4];
    }


    public static void main(String[] args) {
        int[] array = {3,2,1,0};

        List<Integer> A = new ArrayList<>();

//        A.add(2);
        A.add(1);
        A.add(0);
        List<Integer> B = new ArrayList<>();
        List<Integer> C = new ArrayList<>();
        hanota(A,B,C);
        System.out.println(C);
    }

    public static void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {

        hanotafun1(A,B,C, A.size());

    }


    /**
     * 汉诺塔
     *
     *
     * 分为三步走
     * 先将 A 中 n-1 个盘子 通过 C 放到 B
     * 再将 A 最后一个盘子放到 C 上
     * 最后将 B 所有的盘子（总体的 n- 1） 个 盘子放到 C
     *
     *
     * @param A 最左边的盘子
     * @param B 中间盘子
     * @param C 最右边的盘子
     * @param index 需要放盘子的个数
     *
     *
     */

    public static void hanotafun1(List<Integer> A, List<Integer> B
            , List<Integer> C,int index) {

        // 考虑 index 为 1 的特殊情况
        if(index==1) {
            int num = A.remove(A.size()-1);
            C.add(num);
            return;
        }

        // 先 讲 C 放到 利用 C 放到 B
        hanotafun1(A,C,B,index-1);

        // 再把 A 最后一个 放入 C 中
        int num = A.remove(A.size()-1);
        C.add(num);

        // 最后把 B 利用A 全部放C中
        hanotafun1(B,A,C,index-1);



    }


    /**
     *
     * 合并两个有序链表
     *递归法
     *
     * 谁小next 就连下一个 (自己的节点和对方节点的总和)
     *
     * @param list1 第一条升序链表
     * @param list2 第二条升序链表
     * @return 返回两条升序链表的总和
     *
     */


    public static LinkedNode mergeTwoLists(LinkedNode list1, LinkedNode list2) {

        return dfs(list1,list2);
    }


    // 递归的重复子问题

    public static  LinkedNode dfs(LinkedNode list1, LinkedNode list2 ) {

        // 递归的出口
        if(list1==null) {
            // 如果为 null
            // 返回对方节点
            return list2;
        }
        if(list2==null) {
            return list1;
        }

        // 递归的方法体

        if(list1.val< list2.val) {
            // 本身连接两个自身下一个节点和其他节点
            list1.next = dfs(list1.next,list2);
            return list1;
        } else {

            list2.next = dfs(list1,list2.next);
            return list2;
        }
    }


    /**
     * 翻转链表
     * 递归实现
     *
     * @param head 头节点
     * @return 返回新的头节点
     */

    public LinkedNode reverseList(LinkedNode head) {
        // 当head 为 null 就返回
        if(head==null) {
            return null;
        }

        if(head.next==null) {
            // 当这个节点的下一个节点为 null 就返回
            //  有点查询的味道在里面
            return head;
        }

        // 把整个新的头节点进行传递
        // 得到新节点为头结点
        // 相当于后序遍历
        LinkedNode newNode= reverseList(head.next);


        //  当前节点的下一个节点的指向自身
        head.next.next=head;


        //  自身的指向修改为  null
        head.next=null;


        // 让 newNode 一直回到节点中
        return newNode;
    }



}
